package medium;

import data.ListNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/5/1 9:28
 */
public class No86_分隔链表 {
    public static void main(String[] args) {
        Solution86 solution86 = new Solution86();
        ListNode head = new ListNode(1);
        head.add(7);
        head.add(6);
        head.add(3);
        head.add(8);
        head.add(9);
        ListNode partition = solution86.partition(head, 6);
        System.out.println(partition);
    }
}

class Solution86 {
    public ListNode partition(ListNode head, int x) {
        // 一次循环
        //搭桥:small,big
        //small桥头
        ListNode small桥头 = new ListNode(-1);
        ListNode big桥头 = new ListNode(-1);
        //桥桩准备
        ListNode small桥桩 = small桥头;
        ListNode big桥桩 = big桥头;
        //桩基准备(数据进来)
        while (head != null) {
            int val = head.val;
            if (val < x) {
                //小桥桩
                small桥桩.next = new ListNode(val);
                //准备打下一个桩基
                small桥桩 = small桥桩.next;
            } else {
                big桥桩.next = new ListNode(val);
                big桥桩 = big桥桩.next;
            }
            head = head.next;
        }
        //small,big两座桥搭建完毕,开始拼接大桥
        small桥桩.next = big桥头.next;
        return small桥头.next;
    }
}



    //public ListNode partition(ListNode head, int x) {
    //    //暴力法,二次循环
    //    //存放<x
    //    List<Integer> small = new ArrayList<>();
    //    //存放>=x
    //    List<Integer> big = new ArrayList<>();
    //    while (head != null) {
    //        int val = head.val;
    //        if (val < x) {
    //            small.add(val);
    //        } else {
    //            big.add(val);
    //        }
    //        head = head.next;
    //    }
    //    
    //    //拼成链表即可
    //    ListNode res = new ListNode(-1);
    //    //遍历拼
    //    for (int data : small) {
    //        addList(res, data);
    //    }
    //    for (int data : big) {
    //        addList(res, data);
    //    }
    //    return res.next;
    //}
    //
    ////将data加入链表
    //public void addList(ListNode listNode, int data) {
    //    while (listNode != null && listNode.next != null) {
    //        listNode = listNode.next;
    //    }
    //    listNode.next = new ListNode(data);
    //}
